package com.com.datastructures.search;

/**
 * Created with IntelliJ IDEA.
 * User: Ngo Lap Thanh
 * Date: 09/05/14
 * Time: 10:49 AM
 * To change this template use File | Settings | File Templates.
 */
public class Search {

    private int data[];
    private int curIndex;


    public Search(int size){
       // (size <= 0) ? throw new RuntimeException("size cannot be <=0 "):;
       if((size <=0)){
            throw new RuntimeException("size cannot be <=0 ");
       }
       data = new int[size];
       curIndex = 0;
    }

    void insert(int item){
        data[curIndex] = item;
        curIndex++; // it always points to next possible position in array.
    }

    void delete(int item){
        int i=0;
        for(i=0;i<curIndex;i++){
           if(item==data[i]){
               System.out.println("Found item: "+ item + " at index: "+i);
               break;
           }
       }
       if(i==curIndex){
           System.out.println("item: "+ item + " cannot be found.");
       }else{
           //Shuffle items to one position up.
           for(int k=i; k<curIndex-1; k++){
               data[k] = data[k+1];
           }
           curIndex--;
       }
    }


    void display(){
      for(int i=0; i<curIndex;i++){
          System.out.println(data[i]);
      }
    }

    boolean find(int item){
        int beg = 0;
        int end = curIndex-1;

        System.out.println("beg: "+ beg);
        System.out.println("end: "+ end);

        while(beg<=end){
           int mid = beg+end/2;
           if(item == data[mid]){
               System.out.println("Found item: "+ item + " at index: "+mid);
               return true;
              // break;
           }else if(item>data[mid]){
               beg = mid+1;
           }else{
               end = mid-1;
           }
        }

        System.out.println("item: "+ item + " cannot be found.");
        return false;
    }








































    public static void main(String args[]){
        Search s = new Search(5);

        s.insert(3);
        s.insert(6);
        s.insert(7);
        s.insert(8);
        s.insert(9);
        //s.insert(10);

        /*s.display();

        s.delete(45);

        s.delete(9);*//*s.display();

        s.delete(45);

        s.delete(9);*/
        s.display();


        if(s.find(9)){

        }





































    }
}
